package com.zhugang.week13.stack;

import java.util.Stack;

/**
 * @program algorithms
 * @description: DailyTemperatures
 * @author: chanzhugang
 * @create: 2022/11/01 21:30
 */
public class DailyTemperatures {

    /**
     * 739 每日温度
     * https://leetcode.cn/problems/daily-temperatures/
     *
     * @param T
     * @return
     */
    public int[] dailyTemperatures(int[] T) {
        /**
         * 暴力求解: 两层for循环，找比外层循环大的数，计算下标差
         */
        int n = T.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (T[j] > T[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
        return result;
    }

    public int[] dailyTemperatures2(int[] T) {
        /**
         * 一般栈中都是未处理的值，如：计算那道题，未计算的值和字符
         * 单调栈解法：画栈的图， 栈中存储的是下标， 未处理的值
         * 如果栈不等于null，并且栈顶元素比当前值小，计算下标差，弹出栈顶元素
         */
        int n = T.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                int index = stack.peek();
                result[index] = i - index;
                stack.pop();
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        DailyTemperatures dailyTemperatures = new DailyTemperatures();
        int[] arr = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        int[] resutl = dailyTemperatures.dailyTemperatures2(arr);
        for (int num : resutl) {
            System.out.println(num);
        }
    }
}